A compiler maps a higher-order computer language into an assembly or machine language. The higher-order computer language must be translated into machine language before it can be executed.
A compiler supports the analysis-synthesis paradigm. The source language is first analyzed into its lexical, grammatical, and semantic components, and after the completion of a number of phases is finally synthesized into functionally equivalent constructs in the target language. When compiling code for a computer program, optimization techniques are used within the compiler to improve the quality of the generated code. The improved quality relates to either a direct saving in the size of the code needed for the program or an increase in the execution performance of the program.
A typical compiler structure is shown in FIG. 1 and illustrates six major phases. The higher-order source code is input to the compiler and the resulting output is assembly code. Each compiler phase may have additional minor subphases. For example, it is not unusual in an optimizing compiler to divide the many optimization strategies into separate modules. If we remove the optimizer phase from the typical compiler structure, as shown in FIG. 1, then the intermediate level text is transformed into assembly language in a straight forward manner. Here the assembly language would not be as efficient with respect to execution time or storage space.
Consider the C computer program fragment as shown in FIG. 2. This portion of a computer program stores a value of zero into successive memory locations pointed to by the pointer p. The straight forward assembly code is shown in FIG. 3 for it target machine of a Digital Equipment Corporation PDP-11 computer. The first instruction updates the memory location with a value of zero, and the second instruction adjusts the memory pointer to the next memory location. The optimized assembly code is shown in FIG. 4 for the same target machine. Here this single instruction moves the value of zero into memory and then updates the pointer to the next memory location, taking advantage of the autoindexing capability of the PDP-11 architecture. This is an addressing mode that references a memory location and then adjusts the register used as the memory pointer. Some instruction architectures provide pre- and post-increment or decrement forms of memory referencing instructions. These instructions have the characteristic of referencing memory and modifying the contents of an address register used in the memory address calculation. The address register side effect is to automatically add or subtract a specified or implied amount to or from the amount in the address register. This class of memory referencing operation may be considered either as special instructions or addressing modes. These operations have been called `Update Instructions`, autoindexing operations, and autoincrement or autodecrement addressing modes. The autoincrement and autodecrement addressing modes provide automatic stepping of an index register value through a sequence of addresses and offer a significant increase in performance.
Some optimization strategies depend on a particular target machine or architectural feature such as autoindexing. The Digital Equipment Corp. VAX-11 and Motorola MC68000 have architectures with some form of autoindexing.
Other optimization strategies are designed specifically independent of the target architecture. An example is moving some computations from inside the bounds of a loop to the outside of the loop.
Source language features may also be designed to improve the quality of code, especially in the absence of optimization. For example, the use of pointers and the increment and decrement operators in the C language provide an alternative to using indexed arrays and indicate opportunities for autoindexing.